package cn.edu.buaa.datrie;

import java.util.TreeSet;

import cn.edu.buaa.common.IndexCacheConstants;


public class DoubleIntegerArray {

	int capacity = 512;
	int[] base = null;
	int[] check = null;
	TreeSet<Integer> freePositions = null;
	
	public DoubleIntegerArray() {
		init(capacity);
	}
	public DoubleIntegerArray(int initialCapacity) {
		this.capacity = initialCapacity;
		init(initialCapacity);
	}
	
	private void init(int initialCapacity) {
		base = new int[initialCapacity];
		check = new int[initialCapacity];
		freePositions = new TreeSet<Integer>();
		
		base[0] = IndexCacheConstants.INITIAL_ROOT_BASE;  // for root
		check[0] = IndexCacheConstants.ROOT_CHECK_VALUE; // for root
		for (int i = 1; i < capacity; i++) {
			base[i] = IndexCacheConstants.EMPTY_VALUE;
			check[i] = IndexCacheConstants.EMPTY_VALUE;
			
			freePositions.add(i);
		}
	}
	
	private void preProcess(int pos) {
		//check refactor
		if (pos > (capacity * 2 / 3)) {
			refactor();
			
		}

		//delete free position
		if (freePositions.contains(pos)) {
			freePositions.remove(pos);
		}
	}
	
	private void refactor() {
		int _capacity = 2 * capacity;
		int[] _base = new int[_capacity];
		int[] _check = new int[_capacity];
		
		for (int i = 0; i < capacity; i++) {
			_base[i] = base[i];
			_check[i] = check[i];
		}
		
		for (int i = capacity; i < _capacity; i++) {
			freePositions.add(i);
		}
		
		capacity = _capacity;
		base = _base;
		check = _check;
	}
	
	public int getFreePosition() {
		return freePositions.first();
	}
	
	public int getFreePosition(int value) {
		return freePositions.higher(value);
	}
	
	public void putFreePosition(int pos) {
		base[pos] = -1;
		check[pos] = -1;
		
		freePositions.add(pos);
	}
	
	public int getSize() {
		return capacity;
	}
	
	public void setBase(int pos, int index) {
		preProcess(pos);
		
		base[pos] = index;
	}
	
	public void setCheck(int pos, int index) {
		preProcess(pos);
		
		check[pos] = index;
	}
	
	public int getBase(int pos) {
		return base[pos];
	}
	
	public int getCheck(int pos) {
		return check[pos];
	}
	
	public int findConsecutiveFree(int minValue, int maxValue) {
		int amount = maxValue - minValue + 1;
		
		Object[] fp = freePositions.toArray();
		for (int i = 0; i < fp.length; i++) {
			int a = (Integer)fp[i];
			int b = (Integer)fp[i+amount-1];
			
			if (a < minValue) {
				continue;
			}
			
			if (a + amount -1 == b) {
				return a;
			}
		}
		
		refactor();
		return findConsecutiveFree(minValue, maxValue);
	}
}
